package com.example.demo.leetcode.zuocheng.heap;

/**
 * @Description 大根堆复习
 * @Author BG490350
 * @Date 2024/3/19 11:02
 **/
public class Heap {

    int [] arr;
    int heapSize;
    int currIndex=0;
    public Heap(int heapSize){
        arr = new int[heapSize];
        this.heapSize = heapSize;
    }

    public void add(int num){
        if(currIndex >= heapSize){
            return;
        }
        arr[currIndex++] = num;
        for(int i=0;i<currIndex;i++){
            heapInsert(i);
        }
    }

    public void heapInsert(int index){
        while(arr[index] > arr[(index-1)/2]){
            swap(index,(index-1)/2);
            index = (index-1)/2;
        }
    }

    public void swap(int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void sort(){
        int tempSize = currIndex-1;
        while(tempSize > 0){
            swap(0,tempSize);
            for(int i=0;i<tempSize;i++){
                heapInsert(i);
            }
            tempSize--;
        }
    }

    public void print(){
        for(int i=0;i<currIndex;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }


    public static void main(String[] args) {
        Heap heap = new Heap(10);
        heap.add(5);
        heap.add(1);
        heap.add(3);
        heap.add(12);
        heap.add(17);
        heap.print();

        heap.sort();
        heap.print();

    }


}
